package leetcode_600;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import helpclass.TreeNode;

/**
 *@author 周杨
 *FindLargestValueInEachTreeRow_515 返回一棵树中每层最大的元素
 *describe:用层次遍历 队列实现 AC 23%
 *2018年9月9日 下午2:09:36
 */
public class FindLargestValueInEachTreeRow_515 {
	 public List<Integer> largestValues(TreeNode root) {
		 List<Integer> res=new ArrayList<Integer>();
		 if(root==null)
			 return res;
	     Queue<TreeNode> queue=new LinkedList<TreeNode>();
	     queue.offer(root);
	     while(!queue.isEmpty()) {
	    	 int size=queue.size();
	    	 int max=Integer.MIN_VALUE;
	    	 while(size>0) {
	    		 TreeNode now=queue.poll();
	    		 max=Math.max(max, now.val);
	    		 if(now.left!=null)
	    			 queue.offer(now.left);
	    		 if(now.right!=null)
	    			 queue.offer(now.right);
	    		 --size;
	    	 }
	    	 res.add(max);
	     }
	     return res;
	 }
}
